package a;


public class DUI {
    int cs=1;//curSize
    int[] h;
    DUI(int capa){
        h=new int[capa+1];
    }
    //上下移
    void up(int i){//索引
        while(i>=1 && h[i]<h[i/2]){
            swap(i,i/2);
            i=i/2;
        }
    }
    void down(int i){
        int ni = -1;
        while(ni!=i){
            //cs跟踪动态大小，后面0的要扔
            if(2*i<cs && h[i]>h[2*i])ni=2*i;
            if(2*i+1<cs && h[i]>h[2*i+1])ni=2*i+1;

            if(ni!=-1){
                swap(i,ni);
                i=ni;
            }else{
                return;
            }
        }
    }
    void swap(int i,int j){
        int t=h[i];
        h[i]=h[j];
        h[j]=t;
    }

    //插新
    void add(int val){
        h[cs]=val;
        up(cs);
        cs++;
    }
    //删最小
    int poll(){
        //顶部是1不是0
        int out = h[1];
        h[1]=h[--cs];
        h[cs]=0;
        down(1);
        return out;
    }
}
